package dp01;

/**
 * 题目：买卖股票的最佳时机 IV
 * 题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/description/
 */
public class Solution15 {
    public int maxProfit(int a, int[] prices) {
        int n = prices.length;
        int j = a+1;
        int[][] f = new int[n][j];
        int[][] g = new int[n][j];
        for (int i = 0; i < j; i++) {
            if(i == 0){
                f[0][i] = -prices[0];
            } else {
                f[0][i] = - 0x3f3f3f3f;
            }
        }
        for (int i = 0; i < j; i++) {
            if(i == 0){
                g[0][i] = 0;
            } else {
                g[0][i] = - 0x3f3f3f3f;
            }
        }
        for (int i = 1; i < n; i++) {
            for (int k = 0; k < j; k++) {
                f[i][k] = Math.max(f[i-1][k],g[i-1][k]-prices[i]);
                g[i][k] = g[i-1][k];
                if(k-1>=0) {
                    g[i][k] = Math.max(g[i][k],f[i-1][k-1]+prices[i]);
                }
            }
        }
        int ret = -Integer.MAX_VALUE;
        for (int i = 0; i < j; i++) {
            ret = Math.max(ret,g[n-1][i]);
        }
        return ret;
    }
}
